// n >= m
// C(n, m) 同余 C(n % p, m % p) * C(n / p, m / p) % p
// 应用P比较小的情况
// EXLucas不要求P为质数
// 复杂度O(P + lognlogP)
struct CRT {
  using i64 = long long;
  using i128 = __int128;

  i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
  }

  i64 work(vector<i64> a, vector<i64> p) {
    assert(a.size() == p.size());
    i64 M = 1, ret = 0;

    for (int i = 0; i < p.size(); i++) {
      M *= p[i];
    }

    for (int i = 0; i < a.size(); i++) {
      i64 Mi = M / p[i];
      i64 x, y;
      i64 iMi = exgcd(Mi, p[i], x, y);
      x = (x % p[i] + p[i]) % p[i];
      ret += (i128)x * Mi * a[i] % M;
    }
    return ret % M;
  }
};
namespace EXLucas {
	CRT crt;
	using i64 = long long;
	i64 x, y;

	i64 power(i64 a, i64 b, i64 p) {
		i64 ret = 1;
		while (b > 0) {
			if (b & 1) {
				ret = ret * a % p;
			}
			b >>= 1;
			a = a * a % p;
		}
		return ret;
	}

	i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
		if (!b) {
			x = 1, y = 0;
			return a;
		}
		i64 d = exgcd(b, a % b, y, x);
		y -= a / b * x;
		return d;
	}

	i64 inv(i64 a, i64 p) {
		exgcd(a, p, x, y);
		return (x % p + p) % p;
	}

	i64 fac(i64 n, i64 p, i64 pk) {
		if (!n) {
			return 1;
		}
		
		i64 ret = 1;
		for (int i = 1; i <= pk; i++) {
			if (i % p) {
				ret = ret * i % p;
			}
		}
		ret = power(ret, n / pk, pk);
		for (int i = 1; i <= n % pk; i++) {
			if (i % p) {
				ret = ret * i % pk;
			}
		}
		return ret * fac(n / p, p, pk) % pk;
	}

	i64 comb(i64 n, i64 m, i64 p, i64 pk) {
		if (n < m) {
			return 0;
		}
		i64 f1 = fac(n, p, pk), f2 = fac(m, p, pk), f3 = fac(n - m, p, pk);
		i64 c = 0;

		for (i64 i = n; i > 0; i /= p) {
			c += i / p;
		}
		for (i64 i = m; i > 0; i /= p) {
			c -= i / p;
		}
		for (i64 i = n - m; i > 0; i /= p) {
			c -= i / p;
		}
		return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * power(p, c, pk) % pk;
	}

	i64 work(i64 n, i64 m, i64 P) {
		vector<i64> a, p;
		for (i64 i = 2; i * i <= P; i++) {
			if (P % i == 0) {
				i64 v = 1;
				while (P % i == 0) {
					P /= i;
					v *= i;
				}
				if (v != 1) {
					a.push_back(comb(n, m, i, v));
					p.push_back(v);
				}
			}
		}
		if (P > 1) {
			a.push_back(comb(n, m, P, P));
			p.push_back(P);
		}
		return crt.work(a, p);
	}
}